130. 被围绕的区域

发表于 | 分类于 | 阅读次数：

链接：https://leetcode-cn.com/problems/surrounded-regions/

题目描述

给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。

找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

1
2
3
4
5
6
7
8
9
10
11
12
示例:

X X X X
X O O X
X X O X
X O X X
运行你的函数后，矩阵变为：

X X X X
X X X X
X X X X
X O X X

解释:

被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution(object):
    def __init__(self):
        # 小技巧分别表示左下右上
        self.directs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        self.visited = None
        self.result_all = None
        # 分别表示边界
        self.m = 0
        self.n = 0

    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        self.print_b(board)
        print()
        print()
        print()
        self.result_all = []
        self.visited = [[0] * len(board[0]) for _ in range(len(board))]
        self.m = len(board)
        if len(board) == 0:
            return 0
        self.n = len(board[0])
        for i in range(len(board)):
            for j in range(len(board[i])):
                if board[i][j] == 'O' and self.visited[i][j] == 0:
                    result = self.dfs(board, i, j, [])
                    self.result_all.append(result[:])

        print(self.result_all)
        print()
        for i in range(len(self.visited)):
            print(self.visited[i])
        print()

        for res in self.result_all:
            if not self.list_boundary_validate(res):
                continue
            for x, y in res:
                board[x][y] = 'X'
        return board

    def dfs(self, board, x, y, result):
        result.append((x, y))
        self.visited[x][y] = 1
        for i in range(4):
            new_x = x + self.directs[i][0]
            new_y = y + self.directs[i][1]
            if self.in_area(new_x, new_y) and board[new_x][new_y] == 'O' and self.visited[new_x][new_y] == 0:
                self.dfs(board, new_x, new_y, result)
        return result

    def list_boundary_validate(self, steps):
        for x, y in steps:
            if self.in_boundary(x, y):
                return False
        return True

    def in_boundary(self, x, y):
        return x == 0 or x == self.m - 1 or y == 0 or y == self.n - 1

    def in_area(self, x, y):
        return 0 <= x < self.m and 0 <= y < self.n

    def print_b(self, board):
        for i in range(len(board)):
            print(board[i])
        print()